#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};


// 合并两个
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if(list1 == nullptr) return list2;
    if(list2 == nullptr) return list1;
    if(list1->val <= list2->val){
        ListNode* p = list1->next;
        list1->next = mergeTwoLists(p, list2);
        return list1;
    }else{
        ListNode* p = list2->next;
        list2->next = mergeTwoLists(p, list1);
        return list2;
    }
}

// 合并k个
ListNode* mk(vector<ListNode*>& lists, int n){
    if(n == 0) return nullptr;
    if(n == 1) return lists[0];
    vector<ListNode*> small_list;
    int i;
    for(i=0;i<n && i+1 < n;i+=2){
        small_list.push_back(mergeTwoLists(lists[i], lists[i+1]));
    }
    if(i == n-1){
        small_list.push_back(lists[i]);
        return mk(small_list, n + 1 >> 1);
    } 
    return mk(small_list, n >> 1);
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    return mk(lists, lists.size());
}